'''
Created on Aug 3, 2011

@author: anupams
'''
from com.anupam.graphs.GraphsAnupam import SampleGraphObject

class PrimsMST(object):
  """
    Class for finding Minimum Spanning Tress, Using Prims algorithm.
    
  """

#    TODO(anupam) : Remove the discovered vertex from adjucancy list of 
#                   repective vertex, so that number of comparisons done
#                   while checking earlier added edges to MST (for lesser a 
#                   weighted edge) are within nlog(n) range.

  def __init__(self, graphDict, nodes):
    """
    Default constructor of the class.
    
    Args:
      graphDict : Adjucancy list of the graph
      nodes : graph node objects @see{ColoredGraphNode}
    """
    self.graphDict = graphDict
    self.nodes = nodes
    self.MSTEdges = []
    self.tempEdgeAlreadydiscovered = {}
    self.totalWeight = 0

  def __checkEdgeColor(self, edge):
    """
      Checks the color of edge. Grey color means the edge is already traversed.
      
      Args:
        edge : A dict representing edge between two vertex.
    """
    temp = self.tempEdgeAlreadydiscovered.get(edge)
    if temp and temp == 'Grey':
      return True
    return False

  def __checkVertexColor(self, rightVertex):
    """
    Checks the vertex color. Grey color means vertex is already included in
    one of the edges of MST.
    
    Args:
      rightVertex : Name of the vertex to be inspected.
    """
    if rightVertex and self.nodes[rightVertex].color == 'Grey':
      return True
    return False

  def __getleastWeightEdge(self, vertex):
    """
    Gets a valid edge , with least weight,orginating from the vertex.
    A valid edge is the one satisfying these conditions:
      a) Edge should not be Grey colored.
      b) Edge should not be connecting two Grey colored vertex.
      c) Edge should be of least weight in the adjucancy list of vertex.

    Args:
      vertex : The originating vertex from which least weighted edge is to be found.
    
    return: 
      The edge satisfying above conditions or None value.
    """
    adjucancyList = self.graphDict.get(vertex)
    smallest = None
    for i in range(0, len(adjucancyList)):
      currentNode = adjucancyList[i]
      currentEdge = vertex + currentNode['childname']
      if (not self.__checkEdgeColor(currentEdge) and
          not self.__checkVertexColor(currentNode['childname'])):
        if not smallest:
          smallest = currentNode
        elif smallest['weight'] >= currentNode['weight']:
          smallest = currentNode

    if smallest:
      smallestEdge = {}
      smallestEdge['leftVertex'] = vertex
      smallestEdge['rightVertex'] = smallest['childname']
      smallestEdge['weight'] = smallest['weight']
      return smallestEdge
    return None

  def __checkAndInsert(self, edgeToInsert):
    """
    This method checks the adjucancy list of right vertex , of all the edges
    part of MST. Any valid edge passing the checks in @see: __getleastWeightEdge
    and less  then edgeToInsert in terms of weight is selected. A None return
    value indicates that all the vertex are covered and MST has been obtained.
    
    Args:
      edgeToInsert : Edge to be inserted.
    
    Return:
      edge finally selected to be part of MST. None if all vertex are covered.
    """
    size = len(self.MSTEdges)
    if size:
      i = size - 1
      edge = None
      while i >= 0:
        vertexName = self.MSTEdges[i]['rightVertex']
        edge = self.__getleastWeightEdge(vertexName)
        if not edgeToInsert:
          edgeToInsert = edge
        if edge:
          if edge['weight'] < edgeToInsert['weight']:
            edgeToInsert = edge
        i = i - 1
      
      vertexName = self.MSTEdges[0]['leftVertex']
      edge = self.__getleastWeightEdge(vertexName)
      if edge:
        if edge['weight'] < edgeToInsert['weight']:
          edgeToInsert = edge
      
    return edgeToInsert

  def processGraph(self, vertexToProcess):
    """
    Generates the MST of the grah.
    
    Args:
      vertexToProcess : Name of the vertex , to be used as starting point. 
    """
    while vertexToProcess:
      ## Obtain the edge with least weight
      edgeToInsert = self.__getleastWeightEdge(vertexToProcess)
      ## Check weather any of the right vertex in MST edges have a valid vertex
      ## with lower weight.
      edgeToInsert = self.__checkAndInsert(edgeToInsert)
      ## None value indicates that all the vertex are covered and MST is available.

      if edgeToInsert:
        leftVertex = edgeToInsert['leftVertex']
        rightVertex = edgeToInsert['rightVertex']
        self.MSTEdges.append(edgeToInsert)

        ## Color the vertex so that any edge terminating at these vertex
        ## is not considered for MST. 
        self.nodes[leftVertex].color = 'Grey'
        self.nodes[rightVertex].color = 'Grey'

        ## Color the edge to be added to MST so that it's not added to MST again.
        self.tempEdgeAlreadydiscovered[leftVertex + rightVertex] = 'Grey'
        self.tempEdgeAlreadydiscovered[rightVertex + leftVertex] = 'Grey'

        self.totalWeight = self.totalWeight + edgeToInsert['weight']

        ## Set the right vertex of last added edge to MST , as next vertex
        ## to process
        vertexToProcess = rightVertex
      else :
        ## No more vertex left to discover, MST is complete.
        break

if __name__ == '__main__':
  directedGraphSample = SampleGraphObject()
  graphDict = directedGraphSample.undirectedGraphKruskals()
  
  ## Inputing any of the vertex as starting point should
  ## result in same cumulitive edge weight of MST.
  startingVertex = 'h'
  traverse = PrimsMST(graphDict, directedGraphSample.nodes)
  traverse.processGraph(startingVertex)
  print traverse.MSTEdges
  print traverse.totalWeight

